// 链表 的 技巧 与 常用方法
// 1.画图 - 链表的题目大多数都是模拟题，画图能够使模拟过程更加清晰
// 2.引入虚拟头结点 newHead，目的是为了让尾指针具备一般性，一个循环搞定代码
// 3.不吝啬空间，敢于定义变量 prev, next等：prev - 前边链的尾指针  next - 后边链的头指针 有头有尾，不怕链断
// 4.快慢双指针 - 判断环，找环的入口，找链表中的倒数第 n 个节点
// 5.创建新节点
// 6.尾插法 - 定义尾节点 tail，维护尾节点
// 7.头插法 - 引入虚拟头结点 newHead: node -> newHead.next, newHead.next -> node

// 例题 3：
// 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
//
//        L0 → L1 → … → Ln - 1 → Ln
//        请将其重新排列后变为：
//
//        L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
//        不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
//
//        示例 1：
//
//        输入：head = [1,2,3,4]
//        输出：[1,4,2,3]
//        示例 2：
//
//        输入：head = [1,2,3,4,5]
//        输出：[1,5,2,4,3]
//
//        提示：
//
//        链表的长度范围为 [1, 5 * 104]
//        1 <= node.val <= 1000

// 解题思路：
// 使用快慢双指针的方法，找到中间点 - 可以引入虚拟头结点，这样就能使中间点左边的链至多比右边的链多一个节点，这样方便后续合并
// 使用头插法，逆序后半段链:
// cur.next = newHead.next; newHead.next = cur; cur = next; next = cur.next;
// 最后再合并两个链表 - 最多剩最后一个节点，特判一下即可

public class ReorderList {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) return;
        // 快慢双指针找中间节点
        ListNode newHead1 = new ListNode(0);
        newHead1.next = head;
        ListNode slow = newHead1;
        ListNode fast = newHead1;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 头插法逆序链表
        ListNode newHead2 = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null;//  将两个链表拆开
        ListNode next = cur.next;
        while(cur != null){
            cur.next = newHead2.next;
            newHead2.next = cur;
            cur = next;
            if(cur != null) next = cur.next;
        }
        // 合并两个链表
        ListNode cur1 = head;
        ListNode cur2 = newHead2.next;
        cur = newHead1;
        while(cur1 != null && cur2 != null){
            cur.next = cur1;
            cur = cur.next;
            cur1 = cur1.next;
            cur.next = cur2;
            cur = cur.next;
            cur2 = cur2.next;
        }
        if(cur1 != null) cur.next = cur1;
    }
}
